class Solution(object):
    def knightProbability(self, N, K, r, c):#N棋盘 K移动次数 (r,c)初始位置
        
        dp = [[0] * N for _ in range(N)]#f[][][steps-1]的概率
        #print(dp)
        dp[r][c] = 1    #概率初始化
        for _ in range(K):#移动次数
            dp2 = [[0] * N for _ in range(N)]#f[][][steps]的概率
            for r, row in enumerate(dp):#枚举dp的元素r=下标 row=元素
                print(r,row)
                for c, val in enumerate(row):#枚举row的元素c=下标 val=元素
                    print(r,c)
                    for dr, dc in ((2,1),(2,-1),(-2,1),(-2,-1),
                                   (1,2),(1,-2),(-1,2),(-1,-2)):#遍历位置
                        if 0 <= r + dr < N and 0 <= c + dc < N:#判断是否出棋盘
                            print(r + dr,c + dc)
                            dp2[r+dr][c+dc] += val / 8.0#f[][][steps]的概率
            dp = dp2#移动次数[steps-1]与[steps]的交替
        print(dp)
        return sum(map(sum, dp))#对dp的每一个元素进行求和之后再求和
'''

        #@functools.lru_cache(None)
        step = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]#变化
        def dfs(r, c, counts):
            if r < 0 or r > N - 1 or c < 0 or c > N - 1:#判断初始条件是否出界
                return 0
            if counts == K:#判断移动次数是否达到K  递归出口
                return 1
            res = 0#计数器
            for i, j in step:#遍历八个位置
                res += dfs(r + i, c + j, counts + 1)#递归和  在棋盘内的概率相加
            return res / 8#返回最终的概率
        return dfs(r, c, 0)  
'''
a=Solution()
print(a.knightProbability(3,2,0,0))
